package com.剑指offer.第四章;

/**
 * 如果给定一个链表，请如何删除链表中的倒数第k个节点? 要求只能遍历一次
 *
 * 前后双指针 的经典应用是查询链表中倒数第k个节点。先让第1个指针从链表中的头节点开始朝着指向下一个节点的指针先移动k-1步
 * ，然后第2个指针指向链表的头节点，再让他们以相同的速度移动。当第一个指针到达尾节点时，第二个指针正好指向倒数第k个节点
 *
 */
public class 删除倒数第k个节点 {

    public static ListNode resolve(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        /**
         * 使用双指针、第一个指向头部 第二个指向哨兵节点 第二个指针需要是第k+1个节点
         */
        ListNode start = head;
        ListNode back = dummy;
        /**
         * 先移动第一个指针 移动n步
         * 让两个指针的距离保持k
         */
        for (int i = 0; i < n; i++) {
            start = start.next;
        }

        while (start != null) {
            start = start.next;
            back = back.next;
        }
        back.next = back.next.next;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        ListNode p5 = new ListNode(5);
        head.next = p1;
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;

        head = resolve(head, 1);

        ListNode fist = head;
        while (fist != null) {
            System.out.println(fist.val);
            fist = fist.next;
        }
    }

}
